package com.company.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class KthSmallest {
    public int kthSmallest(TreeNode root, int k) {
        //中序遍历的第k个元素
        if (root==null) {
            return 0;
        }
        List<Integer> list = inTraverse(root);
        if (list.size()>k) {
            return list.get(k);
        }
        return  0;
    }
    public List<Integer> inTraverse(TreeNode root){
        List<Integer> result = new ArrayList<>();

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        TreeNode node = root;
        while (!stack.isEmpty()){
            while (node.left!=null){
                stack.push(node.left);
                node = stack.peek();
            }
            //没有左子树了  读取当前节点
            node = stack.pop();
            result.add(node.val);
            //右子树 进行递归
            if (node.right != null) {
                stack.push(node.right);
                node = stack.peek();
            }
        }
        System.out.println(result);
        return result;

    }
}
